package algotithm.jianzhioffer.test10;

/**
 * @author zhouyanxiang
 * @Date 2020-12-2020/12/14-14:13
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 48;
        int x = solution.fib(n);
        System.out.println(x);
    }

    public int fib(int n) {
        int a = 0, b = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    // 可以过，但是还可以优化空间，用O（1）的空间复杂度就行
    /*public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2] ) % 1000000007;
        }
        return dp[n];
    }*/

    // 迭代的超出时间限制
    /*public int fib(int n) {
        if (n == 1 || n == 0) {
            return n;
        }
        return fib(n-1) + fib(n-2);
    }*/

}
